package sort;

import util.Comparator;

import java.util.PriorityQueue;

/**
 * @author Liaorun
 */
public class SortArrayDistanceLessK implements Sortable {

    public static void main(String[] args) {

        Comparator comparator = new Comparator(10, 10, 5);
        comparator.start(new SortArrayDistanceLessK());
    }

    @Override
    public void sort(int[] arr) {

    }

    @Override
    public void sort(int[] arr, int k) {
        sortedArrDistanceLessK(arr, k);
    }

    public void sortedArrDistanceLessK(int[] arr, int k) {
        // 默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        int index = 0;

        // 报k 个数放到堆中，或者 所有的的数都放进去
        // 这里是 <= 号，假设数组足够长，k == 5,就会一开始放 6个数进去，因为 6个数的最大距离为5
        for (; index <= Math.min(arr.length - 1, k); index++) {
            heap.add(arr[index]);
        }

        int i = 0;
        for (; index < arr.length; i++, index++) {
            // 如果数组中还有值没有放到队中，就拿一个放进去
            heap.add(arr[index]);

            // 确定的最小值放到正确的位置，然后堆会自己堆化
            arr[i] = heap.poll();
        }

        // arr 数组所有的数都经过小根堆排序了，
        // 还有数在堆中，把他们全部弹出来放回原数组
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }
}
